#ifdef LOCAL
#include "grader.cpp"
#endif

/*
颜色约定：
1. 还未访问（测量距离的临时标记）
2. 已经访问，还未离开
3. 已经访问，已经离开
*/

#include "graph.h"
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
constexpr int MaxN = 2e2 + 5;
int n;
int answer[MaxN];
int floyd[MaxN][MaxN];
std::vector<int> hisId;
std::vector<int> hisAfter;
std::vector<int> hisBefore;
std::vector<int> g[MaxN];
// 基于未知无向连通图带版本回滚的线性移动函数
void MovePro(const int &u, const int &withColor = Color())
{
    Move(u, withColor == -1 ? Color() : withColor);
    hisAfter.clear();
    hisBefore.push_back(LastRoad());
}
// 撤销移动
void Undo(const int &cnt = 1, const int &withColor = -1)
{
    for (int _ = 1; _ <= cnt && !hisBefore.empty(); _++)
    {
        Move(*hisBefore.rbegin(), withColor == -1 ? Color() : withColor);
        hisAfter.push_back(LastRoad());
        hisBefore.pop_back();
    }
}
// 重做移动
void Redo(const int &cnt = 1, const int &withColor = -1)
{
    for (int _ = 1; _ <= cnt && !hisAfter.empty(); _++)
    {
        Move(*hisAfter.rbegin(), withColor == -1 ? Color() : withColor);
        hisBefore.push_back(LastRoad());
        hisAfter.pop_back();
    }
}
// 染色当前节点，不产生版本信息
void ColorNow(const int &v)
{
    Move(1, v);
    Move(LastRoad(), Color());
}
void solve(int preCurId)
{
    int thisColor = Color();
    // 新节点
    if (thisColor == 1)
    {
        // 分配编号
        int thisCurId = ++n;
        // 添加历史
        hisId.push_back(thisCurId);
        // 边的数量
        int nodeCount = NumberOfRoads();
        for (int i = 1; i <= nodeCount; i++)
        {
            // 移动
            MovePro(i, 2);
            // 递归计算
            solve(thisCurId);
            // 撤销
            Undo(1);
        }
        ColorNow(3);
        // 删除历史
        hisId.pop_back();
    }
    // 老节点
    if (thisColor == 2)
    {
        for (int i = 1; i < int(hisBefore.size()); i++)
        {
            // 回到上一个节点
            Undo(1);
            // 撤销到尝试的距离
            Undo(i, 1);
            // 回溯到当前节点
            Redo(i + 1);
            // 距离够了
            if (Color() == 1)
            {
                // 撤销所有更改
                Undo(i + 1, 2);
                Redo(i + 1);
                // 添加边
                int thisCurId = hisId[int(hisId.size()) - i];
                g[thisCurId].push_back(preCurId);
                g[preCurId].push_back(thisCurId);
                return;
            }
        }
        // 在根节点（根节点没有上一步信息，无法回滚）
        Undo(hisBefore.size(), 2);
        // 回溯到当前节点
        Redo(hisAfter.size());
        int thisCurId = hisId[0];
        g[thisCurId].push_back(preCurId);
        g[preCurId].push_back(thisCurId);
    }
}
void Inspect(int R)
{
    solve(-1);
#ifdef LOCAL
    printf("%d\n", n);
    for (int u = 1; u <= n; u++)
    {
        for (const auto &v : g[u])
        {
            if (u < v)
            {
                printf("%d <-> %d\n", u, v);
            }
        }
    }
#endif
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            floyd[i][j] = 0x3f3f'3f3f;
        }
        floyd[i][i] = 0;
    }
    for (int u = 1; u <= n; u++)
    {
        for (const auto &v : g[u])
        {
            floyd[u][v] = 1;
        }
    }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                floyd[i][j] = std::min(floyd[i][j], floyd[i][k] + floyd[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i - 1; j++)
        {
            answer[floyd[i][j]]++;
        }
    }
    for (int i = 1; i <= R; i++)
    {
        Answer(i, answer[i]);
    }
}
